This invention relates to a cognitive packet network and method of packet switching packets in a data packet communication environment having a plurality of digital packet transmission stations interconnectable in paths.
Most communication networks have been arranged to provide either a connection-oriented service or a connectionless service. In a connection-oriented service, a circuit is established between a source node and a destination node of the network, and all the data transferred between the source node and destination node travels via the links and nodes incorporated in the circuit. The circuit is released only when the call is terminated. Such an arrangement has the advantage that all the data arrives at the destination node in the same order as it is transmitted from the source node. In a connectionless service, data is transmitted between a source node and a destination node via packets or datagrams which each include the address of the destination node and travel along one or more paths through the network to the destination node, the paths chosen generally depend upon the conditions in the network. Accordingly, the packets from the source node can reach the destination node via a multiplicity of paths through the network, each having different delays so that the order in which the packets are received at the destination node does not necessarily correspond to the order in which the packets are transmitted from the source node. Accordingly, facilities are normally required to reorder the data receive by a destination node of such a network.
A wide area network (WAN) is sometimes referred to as a xe2x80x9cnetwork of networksxe2x80x9d. The Internet is a WAN that has become popular.
ARPANET (Advanced Research Projects Agency Network) was the first network in the USA to use packet switching technology. It was set up as an experimental network to investigate system resource sharing in 1969, and has given rise to the Internet which currently connects nodes throughout the world. Routes are generated in the Internet in a distributed fashion. Each node maintains a network database, which includes a complete network topology. The Internet uses datagrams, so that circuits do not have to be construed. Each node calculates a Routing Table (RT) from its delay table and topology database; this routing table contains the best outgoing link to all destination nodes in the network. An end-to-end protocol known as TCP is used to ensure that packets are received at the destination in the correct order, and that losses are detected.
The Internet is based upon a transmission protocol known as xe2x80x9cTransmission Control Protocol/Internet Protocolxe2x80x9d (or xe2x80x9cTCP/IPxe2x80x9d for short), which sends packets of data between a host machine, e.g. a sever computer on the Internet, and a client machine, e.g. a user""s personal computer connected to the Internet. The World-Wide-Web (WWW) is an Internet interface protocol which is supported by the same TCP/IP transmission protocol.
The following U.S. patents relate to network communications: Prior U.S. Pat. No. 6,038,230 relates to time management in a system in which packets are transmitted only at predetermined clocked instants of time (xe2x80x9cpre-defined periodic intervalsxe2x80x9d), as when dealing with the transmission of voice packets over a network. It describes a scheme for automatically inserting packets into the first available subsequent interval on each pre-determined link, whenever packets are delayed and thus cannot be transmitted within their predetermined time interval.
In contrast, the present invention does not assume that there are any pre-defined periodic time intervals for packet transmission but deals with packet routing through the network rather than with the selection of specific time intervals for packet transmission. It determines adaptively the sequence of nodes and links that a packet must traverse.
In U.S. Pat. No. 6,044,062 to Brownrigg et al., a routing scheme for a wireless network can be used to connect to the Internet. The purpose of the system is to allow xe2x80x9cclientsxe2x80x9d to communicate via wireless with a xe2x80x9cserverxe2x80x9d using data packets, either directly (one hop), or indirectly by communicating via other xe2x80x9cclientsxe2x80x9d. It optimizes the communication by seeking to minimize the number of hops, or it can also factor in traffic load and link reliability issues. Each client creates and maintains a route (path) to the server. The routing algorithm portion of this patent specifies that if a client cannot reach a server directly, it probes all of its neighbors. As it does so, if any neighbor has an existing route to a server, then this information will propagate to the server which will add the new client to its routing table. Information about the route can then be forwarded from the immediate neighbor down to the new client so that both the server and the client have the route. The routing scheme proposed here is very similar to the one in U.S. Pat. No. 5,142,531, below, as adapted to the particular wireless environment. Thus the present patent""s contribution is related specifically to the broadcasting wireless environment, rather than to routing issues.
U.S. Pat. No. 5,142,531 to Kirby proposes that each node NS in a packet switching network will contain a table where each row in the table corresponds to a possible destination node, say NA. Each row in the table has two entries. Consider the row corresponding to destination node NA:
the first entry is the name of the immediate neighbor node of NS which has an ultimate connection to destination NA with the minimum number of hops (intermediate nodes),
the second entry is the name of the immediate neighbor node of which provides the currently known shortest delay from NS to NA.
The method uses both lists to build a route from source to destination in advance of the actual transmission of a sequence of packets from source to destination. In order to do this, the source sends out a BUILD packet which is routed hop-by-hop (node-by-node) from source to destination according to a very specific scheme.
At any step of BUILD""s route, if the next node designated by List 1 and List 2 is the same, then it is selected as the next node. If the two are not identical, then BUILD goes indirectly (i.e. in more than one step) to the node indicated in List 1 which is now included in the route, but first uses the link (next node) designated in the appropriate List 2.
In addition to this specific algorithm used by the BUILD packet, this patent also proposes a manner in which the contents of List 1 and List 2 are to be maintained and updated. All nodes are organized so as to propagate hop count and delay information to all other nodes in a periodic fashion.
Each neighboring node will pass on to its neighbors its known hop count information to its possible destinations, while the receiving neighbor will simply add 1 to that hop count to deduce its own hop count distance to the possible destinations. Presumably the identity of the neighbor having minimum hop count to destination, which is the information stored in List 1, will be selected from all the available values. Delay information will similarly be aggregated by propagating delay information from neighbors and adding to it the link delay between adjacent neighbors. Similarly, the neighbor providing the minimum delay to a destination should presumably be entered into the appropriate row in List 2.
The patent descriptions also indicates that the information communication between nodes will only take place when a nodes own List 1 or List 2 change, and in addition to that a node will confirm periodically to all of its neighbors that it xe2x80x9cexistsxe2x80x9dxe2x80x94i.e. that it is still operational.
In addition to this, when a route is established by a BUILD packet, and the BUILD packet reaches the ultimate destination, and ACKNOWLEDGE packet is sent back to the source so that the source can know that the route is established so that the normal transmission of packets can begin.
In contrast, the present invention uses xe2x80x9ccognitivexe2x80x9d or xe2x80x9csmartxe2x80x9d packets to search for routes towards the destination using delay and loss information. When a smart packet traverses the network and enters some node, a specific reinforcement learning algorithm is activated and the delay and loss information is used to determine the appropriate outgoing link from the node. The cognitive packet stores the identity of each successive node it visits. It also stores the sequence of effective transmission delays it experiences and which correspond to the successive nodes it has visited. It can store the delays simply by consulting the clock at a node it leaves before being placed in a link output queue, and then consulting the clock at the node it enters when it is selected for processing by the service mechanism of the node it has reached. This procedure is applied at each new node visited by the cognitive packet (CP) until (1) either the destination is reached, or (2) the total time the cognitive packet has spent in the network without reaching the destination has exceeded a xe2x80x9cTime-Outxe2x80x9d value.
In the latter case, the cognitive packet is discarded. In the former case an ACK (Acknowledgement) packet is generated by the destination. The ACK contains the inverse route that the ACK will traverse from destination to source, which is merely the inverse of the forward route that the cognitive packet took after removal of the longest cycle (if any) in the route, where xe2x80x9clengthxe2x80x9d of the cycle is expressed to include delay (rather than just the number of hops). The ACK also contains the delay information: the information about delays between adjacent nodes, as experienced by the cognitive packet. As the ACK traverses nodes, it deposits the delay information in the Mailboxes (MB) of the nodes it visits.
Once the ACK reaches the source node, subsequent packets can be forwarded to the destination using the successful route that the ACK has brought back. Subsequent cognitive packets can also use the delay information stored in the intermediate nodes to search for better routes using the same reinforcement learning algorithm.
U.S. Pat. No. 5,142,531 does not address the issue of packet losses which is addressed by the cognitive packet network.
U.S. Pat. No. 5,263,080 to Jones et al. is an improvement on pay telephone systems. U.S. Pat. No. 5,680,551 to Martino, II introduces a uniform messaging interface for heterogeneous applications running on different and/or heterogeneous computing platforms. It does not propose a communication or packet switching mechanism, but can make use of a wide variety of underlying communication mechanisms.
U.S. Pat. No. 5,740,156 to Tanabe et al. pertains to packet switching with fixed length packets such as ATM. It therefore exploits the synchronous nature (clocked) of the communication medium. Encoded header information in the packet is used in each switch to determine the next switch the packet should enter.
It thus requires a fixed network topology (i.e. one in which all nodes are organized with respect to each other in a fixed manner) so that the path from each source to each destination is in fact known in advanced.
U.S. Pat. No. 5,812,528 to VanDervort pertains to packet switching with fixed length packets and specifically ATM. This is a highly standardized connection oriented communication technology which establishes virtual circuits along a pre-selected set of switching nodes. The patent proposes a round trip delay measurement scheme that can be used in optimizing traffic flows in ATM.
U.S. Pat. No. 6,041,038 to Aimoto pertains to packet switching with fixed length packets and specifically to ATM. The scheme described here is one which allows ATM switches to store information about the priority with which cells coming from some particular source may be discarded in case of congestion at the switch. This information is provided to the switches by source units which do not reserve bandwidth but rather indicate cell discard priorities.
U.S. Pat. No. 5,936,939 to DesJardins et al. describes a congestion control mechanism based on discarding packets which contain certain data cells. The mechanism is implemented in special routers or network nodes. The packets which are selected for discarding are those which contain cells pertaining to streams of data which had not been received prior to the enabling of the discarding mechanism for this particular stream. Thus in case of congestion, streams of data which were previously being transmitted are protected, while new incoming streams can be discarded to reduce congestion inside the network.
U.S. Pat. No. 5,844,888 to Markkula Jr. et al. describes a structure of hardware units called xe2x80x9ccellsxe2x80x9d in this patent, but this should not be confused with ATM cells which are small fixed-length packets transmitted in a network. In this patent, these hardware units all have identical architecture and are programmed to carry out different tasks for sensing and control of a distributed system such as a home power distribution system, or a home air conditioning system, or an industrial system, or the like. All of these hardware units typically use a single power system both as their own power supply and as their own communication system to communicate with other hardware units. These hardware units can then be networked through one or several interconnected power systems to achieve sensing and control functions, such as turning lights on and off when it gets dark or light, or turning on air conditioner on and off. The sensor hardware units and the actuator hardware units will typically be at different locations and will communicate with each other.
The communication protocol between cells is closely related to the xe2x80x9crandom accessxe2x80x9d or Ethernet type protocols. The technique is based on packet transmission, collision detection and exponential backoff. This is due to the fact that a group of common shared power supply lines are used as the medium for communication. Routes for packets going between different hardware units are established by packet broadcasting from the source hardware unit until the destination cells are reached. Provision is also made for discarding packets which experience a repeated number of collisions in a particular subnetwork. Thus the system operates as an interconnection of Ethernet-like sub-networks (random access), rather than as a meshed packet switching network which is the architecture considered in CPN.
U.S. Pat. Nos. 5,475,687 to Markkula, Jr. et al. and U.S. Pat. No. 4,918,690 to Markkula, Jr. et al. are similar to U.S. Pat. No. 5,844,888. U.S. Pat. No. 6,016,319 to Kshirsagar et al. describes a method for carrying xe2x80x9cconnectionlessxe2x80x9d packets or datagrams over an ATM network. ATM networks set up a connection via a set of ATM switches from source to sink and back. On the other hand, the cognition packet network invention describes a xe2x80x9cconnectionlessxe2x80x9d technique which differs from IP.
U.S. Pat. No. 6,038,216 to Packer proposes a specific data rate control mechanism destined to modify the existing rate control mechanisms in TCP/IP and uses the delay on acknowledgement packets as a way to modulate the incoming source to destination data rate with a larger delay resulting in a smaller data flow rate. The cognitive packet network on the other hand is a replacement for the IP layer and introduces a different manner to handle routing. Thus in a network operating along the CPN principle, this particular invention could be used as an alternative or variant to TCP, just as TCP or some other technique may be used in conjunction with CPN.
U.S. Pat. No. 6,039,245 to Symonds et al. describes a system designed to deal with messages arriving from a variety of external sources, in a variety of external formats. The external formats are translated into a standard internal message format by software called xe2x80x9cmessage routersxe2x80x9d using a relational database. The messages are then routed using the database information to specific message processing programs. The message routers are also used to translate the outgoing messages from the internal format to the specific external format which is needed, and then channeled to external receiving devices. The internal network connection is a standard TCP/IP network while existing public networks are used for external connections.
The method of switching in a network local area having a plurality of routers for routing data packets between source and destination includes the steps of generating a smart data packet having source and destination data and containing a learning algorithm for learning a route from the source to the destination. The smart data packet is transmitted over the network of routers or nodes from the source to the destination for learning the path of routers from the source to the destination and transferring the learned, path of routers from the smart data packet to an acknowledgement packet. The acknowledgement packet which returns along the reverse learned route of the smart data packet to the source. One or more dumb data packets of data are generated at the source having a predetermined route from the acknowledgement packet which dumb data packets are sent along the predetermined route determined by the smart data packet from the source to the destination to form a cognitive packet network using smart data packets, acknowledgement packets and dumb data packets to transmit data from a source to a destination.